With the quick development of new broadband applications in recent years, higher requirements are demanded for transmission and processing of massive information, where the switching network plays an important role. Be it in a traditional network, such as a metropolitan backbone network, or in new types of networks represented by the data center, the switching network plays a crucial role.
Properties of the switching network primarily depend on the traffic scheduling method. The explosive growth of network information has resulted in ever more number of switching ports and ever higher rates thereof, thus renders it ever more difficult for real time collection of information of all the ports. Hence, the design of a traffic scheduling method primarily faces the following challenges and requirements:
(1) Scalability: a good scheduling method needs to satisfy an ever expanding trend of the scale of the switching network;
(2) High throughput: a good scheduling method needs to enable maximum utilization of bandwidth resources and high throughput capacity of the switching network;
(3) Distributed and parallel operations: a good scheduling method needs to minimize cost for collecting port information and to reduce computation complexity.
To meet the afore-mentioned requirements, current scheduling methods for the switching network are categorized as follows:
The first category is the maximum size matching (MSM) algorithm. The basic idea of a MSM algorithm is to maximize the connection number of the input and output ports at each timeslot, so as to make maximum utilization of real time bandwidth. Currently, computation complexity for algorithms in the category is O(N log N), and thus the scalability thereof is not good. In addition, under non-uniform traffic load, the algorithms in the category may result in system instability. While in actual systems, the majority of service flows are non-uniform. Therefore, algorithms in the category do not satisfy the requirements of current switching networks.
The second category is the maximum weight matching algorithm. In view of the defects of the MSM algorithm, an algorithm in the category takes into account real time data information in the system, such as the queue length or the waiting time of the head-of-line packet of each VOQ. In this way, a scheduling algorithm makes further use of more valid information, and provide a high performance under both uniform and non-uniform traffic loads. However, computation complexity for the algorithm in the category is high, generally being O(N2 log N). Therefore, algorithms in the category have poor scalability and do not satisfy the requirements for the switching network.
The third category is the batch scheduling algorithm. A range of consecutive timeslots is stipulated in an algorithm of the category, called a frame. In contrast to the previous two categories of algorithms where the traffic packets are scheduled within each timeslot, a batch scheduling algorithm operates with a frame as a unit and schedules packets within a frame. In this way, the algorithm has a low amortized computational complexity per timeslot, while the traffic statistical characteristics within a given frame are made full use of. However, currently existing algorithms in the category do not realize distribution while reducing the computational complexity in the mean time.
The fourth category is the quasi-static scheduling algorithm. Algorithms in the category emerge in response to avoiding online computation while providing the bandwidth guarantee for each input/output pair. The algorithms are primarily based on the Birkhoff-von Neumann (BvN) decomposition. The scheduling algorithm guarantees the capacity assigned for each input-output pair by the repeated executions of a set of predetermined connection patterns, which are calculated from the average loading of all input-output pairs subject to the fixed total switching capacity. Furthermore, connection patterns are recalculated according to the new matrix when the service matrix substantially changes. A quasi-static scheduling algorithm may achieve 100% throughput with low online computational complexity under smooth traffic. However, when the traffic matrix is fluctuated, the complexity of BvN decomposition is O(N4.5), which gives the system a high computational burden.